package d_scene.a_1_ip_count;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.*;


/**
 * 二分解决
 * m -> 登录ip条数    n -> 网段区间数
 * 时间复杂度    O(mlogn)
 * 空间复杂度    0(n)
 * ------
 * Q: 给你 100万IP 地址数据，如何快速统计不同国家的IP数量呢？
 * 数据格式如下：
 * 1.0.0.0  1.0.0.255   CountryA
 * 2.0.0.0  2.0.0.255   CountryB
 * 3.0.0.0  3.0.0.255   CountryC
 *
 * @author FRSF
 * @since 2025/2/24 20:50
 */
public class Binary {
    public static void main(String[] args) {
        // 1. 加载IP网段数据（已经按起始IP排序）
        List<IPRange> ipRanges = initData();
        // 2.读取登录日志
        List<String> logIps = Arrays.asList("1.0.0.10", "2.0.0.20", "3.0.0.30", "1.0.0.200", "192.168.0.1");
        // 3. 统计登录人数
        Map<String, Integer> countryCounts = new HashMap<>();
        for (String ip : logIps) {
            String country = binaryFindCountryByIp(ipRanges, ipToLong(ip));
            countryCounts.put(country, countryCounts.getOrDefault(country, 0) + 1);
        }
        // 4.输出结果
        for (Map.Entry<String, Integer> entry : countryCounts.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }

    /**
     * 二分查找IP归属
     *
     * @param ipRanges IP网段列表
     * @param ip       目标IP
     * @return Country
     */
    private static String binaryFindCountryByIp(List<IPRange> ipRanges, long ip) {
        int left = 0;
        int right = ipRanges.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            IPRange ipRange = ipRanges.get(mid);
            if (ip >= ipRange.getStartIp() && ip <= ipRange.getEndIp()) {
                return ipRange.getCountry();
            } else if (ip < ipRange.getStartIp()) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return "Unknown";
    }


    /**
     * 网段数据初始化
     *
     * @return List
     */
    private static List<IPRange> initData() {
        List<IPRange> ipRanges = new ArrayList<>();
        ipRanges.add(new IPRange(ipToLong("1.0.0.0"), ipToLong("1.0.0.255"), "CountryA"));
        ipRanges.add(new IPRange(ipToLong("2.0.0.0"), ipToLong("2.0.0.255"), "CountryB"));
        ipRanges.add(new IPRange(ipToLong("3.0.0.0"), ipToLong("3.0.0.255"), "CountryC"));
        return ipRanges;
    }


    /**
     * IP地址转long
     *
     * @param ip IP
     * @return long
     */
    private static long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long result = 0;
        for (int i = 0; i < 4; i++) {
            result = result << 8 | Integer.parseInt(parts[i]);
        }
        return result;
    }


    @Data
    @AllArgsConstructor
    static class IPRange {
        long startIp;
        long endIp;
        String country;
    }
}
